/*
题目: 最长重复子数组
给两个整数数组 nums1 和 nums2 ，返回 两个数组中 公共的 、长度最长的子数组的长度 。
https://leetcode.cn/problems/maximum-length-of-repeated-subarray/
 */
public class FindLength {
    public int findLength(int[] nums1, int[] nums2) {
        //保证 A 数组比较大
        return nums1.length < nums2.length ? searchMaxArr(nums2, nums1) : searchMaxArr(nums1, nums2);
    }

    private int searchMaxArr(int[] A, int[] B) {
        //双尺子法
        int n = A.length;
        int m = B.length;
        int max = 0;

        //    |*|*|*|*|*|
        //|*|*|
        for (int i = 0; i < m; i++) {
            max = Math.max(max, searchMaxLength(A, 0, B, m - i - 1, i + 1));
        }

        //|*|*|*|*|*|
        //  |*|*|
        for (int i = 1; i < n - m + 1; i++) {
            if (max == m) return max;
            max = Math.max(max, searchMaxLength(A, i, B, 0, m));
        }

        //|*|*|*|*|*|
        //        |*|*|
        for (int i = n - m + 1, diff = 1; i < n; i++, diff ++) {
            if (max > m - diff) return max;
            max = Math.max(max, searchMaxLength(A, i, B, 0, m - diff));
        }

        return max;
    }

    private int searchMaxLength(int[] A, int i, int[] B, int j, int diff) {
        //求这两个片段中相同的部分
        int ret = -1;
        int k = 0;
        int cnt = 0;
        while (k < diff) {
            if (A[i + k] == B[j + k]) {
                cnt ++;
            } else {
                ret = Math.max(ret, cnt);
                cnt  = 0;
            }
            k ++;
        }

        return Math.max(ret, cnt);
    }
}
